/*
 * 优先队列，找出滑动窗口中的最大值
 * https://leetcode-cn.com/problems/sliding-window-maximum/
 */

void swap(int** a, int** b) {
    int* tmp = *a;
    *a = *b, *b = tmp;
}

int cmp(int* a, int* b) {
    return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0];
}

struct Heap {
    int** heap;
    int size;
    int capacity;
};

void init(struct Heap* obj, int capacity) {
    obj->size = 0;
    obj->capacity = capacity;
    obj->heap = malloc(sizeof(int*) * (obj->capacity + 1));
    for (int i = 1; i <= obj->capacity; i++) {
        obj->heap[i] = malloc(sizeof(int) * 2); // 存放数组的值和下标
    }
}

void push(struct Heap* obj, int num0, int num1) {
    int sub1 = ++(obj->size), sub2 = sub1 >> 1;
    (obj->heap[sub1])[0] = num0, (obj->heap[sub1])[1] = num1;
    while (sub2 > 0 && cmp(obj->heap[sub2], obj->heap[sub1]) < 0) {
        swap(&(obj->heap[sub1]), &(obj->heap[sub2]));
        sub1 = sub2, sub2 = sub1 >> 1;
    }
}

void pop(struct Heap* obj) {
    int sub = 1;
    swap(&(obj->heap[sub]), &(obj->heap[(obj->size)--]));
    while (sub <= obj->size) {
        int sub1 = sub << 1, sub2 = sub << 1 | 1;
        int maxSub = sub;
        if (sub1 <= obj->size && cmp(obj->heap[maxSub], obj->heap[sub1]) < 0) {
            maxSub = sub1;
        }
        if (sub2 <= obj->size && cmp(obj->heap[maxSub], obj->heap[sub2]) < 0) {
            maxSub = sub2;
        }
        if (sub == maxSub) {
            break;
        }
        swap(&(obj->heap[sub]), &(obj->heap[maxSub]));
        sub = maxSub;
    }
}

int* top(struct Heap* obj) {
    return obj->heap[1];
}
void setFree(struct Heap* obj) {
    for (int i = 1; i <= obj->capacity; i++) {
        free(obj->heap[i]);
    }
    free(obj->heap);
    free(obj);
}

/* k为窗口大小 */
int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {
    struct Heap* que = malloc(sizeof(struct Heap));
    init(que, numsSize);
    for (int i = 0; i < k; i++) {
        push(que, nums[i], i);
    }
    int* res = malloc(sizeof(int) * (numsSize - k + 1));
    *returnSize = 0;
    res[(*returnSize)++] = top(que)[0];

    for (int i = k; i < numsSize; ++i) {
        push(que, nums[i], i);
        while (top(que)[1] <= i - k) {
            pop(que);
        }
        res[(*returnSize)++] = top(que)[0];
    }
    setFree(que);
    return res;
}

/* =================================================================================== */
/* 方法2：
 * 单调队列，k为窗口大小
 */
int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize)
{
    int que[numsSize]; // 单调队列，存放nums元素的下标
    int left = 0, right = 0;
    for (int i = 0; i < k; ++i) {
        while (left < right && nums[i] >= nums[que[right - 1]]) {
            right--; // 如果新进元素比队尾的值大，则直接移出队尾的值
        }
        que[right++] = i; // 将新值放到队尾
    }
    *returnSize = 0;
    int* res = malloc(sizeof(int) * (numsSize - k + 1));
    res[(*returnSize)++] = nums[que[left]];
    for (int j = k; j < numsSize; ++j) {
        while (left < right && nums[j] >= nums[que[right - 1]]) {
            right--;
        }
        que[right++] = j; // 入队
        while (que[left] <= j - k) { // 该元素已不在窗口中
            left++; // 出队
        }
        res[(*returnSize)++] = nums[que[left]]; // 单调递减队列，left为最大值
    }
    return res;
}
